package demo4;

import java.util.Arrays;
import java.util.Comparator;
import java.util.*;
public class Solution {
    //1.编辑距离(动态规划)
    public int minDistance(String word1, String word2) {
        int row = word1.length();
        int col = word2.length();
        int[][] min = new int[row + 1][col + 1];
        //初始化
        for(int i = 0; i <= row; i++) {
            min[i][0] = i;
        }
        for(int i = 1; i <= col; i++) {
            min[0][i] = i;
        }
        //递推
        for(int i = 1; i <= row; i++) {
            for(int j = 1; j <= col; j++) {
                //先求插入和删除中的最小步骤
                min[i][j] = Math.min(min[i][j - 1], min[i - 1][j]) + 1;
                //替换
                if(word1.charAt(i - 1) == word2.charAt(j - 1)) {//相等则不需要替换(不用加1)
                    min[i][j] = Math.min(min[i][j], min[i - 1][j - 1]);
                } else {//不相等
                    min[i][j] = Math.min(min[i][j], min[i - 1][j - 1] + 1);
                }
            }
        }
        return min[row][col];
    }
    //2.不同的子序列(动态规划)
    public int numDistinct(String s, String t) {
        int row = s.length();
        int col = t.length();
        int[][] dp = new int[row + 1][col + 1];
        //初始化
        dp[0][0] = 1;
        //递推
        for(int i = 1; i <= row; i++) {
            dp[i][0] = 1; //初始化第一列
            for(int j = 1; j <= col; j++) {
                if(s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];//使用和不使用第i个字符
                } else { //不相等，就退化到上一级
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[row][col];
    }
    //2.优化
//    public int numDistinct(String s, String t) {
//        int row = s.length();
//        int col = t.length();
//        int[] dp = new int[col + 1];
//        //初始化
//        dp[0] = 1;
//        //递推
//        for(int i = 1; i <= row; i++) {
//            for(int j = col; j > 0; j--) {
//                if(s.charAt(i - 1) == t.charAt(j - 1)) {
//                    dp[j] = dp[j - 1] + dp[j];//使用和不使用第i个字符
//                }
//            }
//        }
//        return dp[col];
//    }
    //2.分割平衡字符串(贪心)
    public int balancedStringSplit(String s) {
        //左右一旦平衡，立马向后分割即可
        //计数器
        int v = 0;//平衡器，遇到R就++,反之则--//为0时说明可以分割
        int count = 0;
        for(int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if(ch == 'R') {
                v++;
            } else {
                v--;
            }
            if(v == 0) {
                count++;
            }
        }
        return count;
    }

    //3.买卖股票的最佳时机 II(贪心)
    public int maxProfit(int[] prices) {
        //只要是收益的，就买股票，这里可以选择第一天先不买
        //到第二天的时候在决定买不买
        int maxfit = 0;
        for(int i = 1; i < prices.length; i++) {
            if(prices[i - 1] < prices[i]) {//买前一天的
                maxfit += prices[i] - prices[i - 1];//获取利润
            }
            //如果不是的就什么也不做
        }
        return maxfit;
    }
    //4.跳跃游戏(贪心)
    public boolean canJump(int[] nums) {
        //记录下每次能够跳到的最远位置
        int len = nums.length;
        if(len == 1) {
            return true;
        }
        int maxJump = nums[0];
        for(int i = 1; i < len; i++) {
            if(maxJump >= i) {//先判断最远位置能不能到达下一个位置
                //能到达就判断当前能到达的最远位置是否大于maxJump
                if(nums[i] + i > maxJump) {
                    maxJump = nums[i] + i;
                }
            }
            if(maxJump >= len - 1) {//若最大距离能到最后一个位置，说明可以
                return true;
            }
        }
        return false;
    }
    //跳跃游戏(贪心 + 优化)
//    public boolean canJump(int[] nums) {
//        int len = nums.length;
//        int max = 0;//当前能到达的最远位置
//        for(int i = 0; i < len; i++) {
//            if(max >= i) { //能到达当前位置
//                max = Math.max(max, nums[i] + i);
//                if(max >= len - 1) {
//                    return true;
//                }
//            }else {
//                break;
//            }
//        }
//        return false;
//    }

    //5.无重复区间(贪心)
    public int eraseOverlapIntervals(int[][] intervals) {
        //按照结束时间又小到大排序（结束时间越早，剩余的时间也就也越多）
        Arrays.sort(intervals, new myCom());
        int count = 1;//至少肯定能执行一个
        int i = 0;
        for(int j = 1; j < intervals.length; j++) {
            //上一个会议的结束时间要小于等于下一个会议的开始时间
            if(intervals[i][1] <= intervals[j][0]) {
                count++;
                i = j;
            }
        }

        return intervals.length - count;
    }
//    //6.图像渲染(回溯)
//    private int row;
//    private int col;
//    private boolean[][] flag;
//    private int book;
//    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
//        //本身可以被上色
//        this.row = image.length;
//        this.col = image[0].length;
//        this.flag = new boolean[row][col];
//        this.book = image[sr][sc];
//        dfs(image, sr, sc, color);
//        return image;
//    }
//    private void dfs(int[][] image, int x, int y, int color) {
//        if(x < 0 || x >= row || y < 0 || y >= col || image[x][y] != book || flag[x][y]) {
//            return;
//        }
//        //上色
//        image[x][y] = color;
//        flag[x][y] = true;
//        dfs(image, x - 1, y, color);
//        dfs(image, x + 1, y, color);
//        dfs(image, x, y - 1, color);
//        dfs(image, x, y + 1, color);
//    }
//    //7.岛屿的周长(回溯)
//    private int row;
//    private int col;
//    private int sum;
//    public int islandPerimeter(int[][] grid) {
//        //遍历先找到第一个岛屿，然后开始dfs
//        this.row = grid.length;
//        this.col = grid[0].length;
//        boolean[][] flag = new boolean[row][col];
//        for(int i = 0; i < row; i++) {
//            for(int j = 0; j < col; j++) {
//                if(grid[i][j] == 1) { //找出一个陆地就可以了
//                    dfs(grid, flag, i, j);
//                    return sum;
//                }
//            }
//        }
//        return sum;
//    }
//    private void dfs(int[][] grid, boolean[][] flag, int x, int y) {
//        //走过的地方就没必要在走了
//        if(x >= 0 && x < row && y >= 0 && y < col && flag[x][y]) {
//            return;
//        }
//        //出界边界或者是到达海面都++
//        if(x < 0 || x >= row || y < 0 || y >= col || grid[x][y] != 1) {
//            sum++;
//            return;
//        }
//        flag[x][y] = true;
//        dfs(grid, flag, x + 1, y);
//        dfs(grid, flag, x - 1, y);
//        dfs(grid, flag, x, y - 1);
//        dfs(grid, flag, x, y + 1);
//    }
//    //8.被围绕的区域(暴力回溯 超时)
//    private int row;
//    private int col;
//    private boolean flag;
//    public void solve(char[][] board) {
//        //找到被包围的o，然后再dfs
//        this.row = board.length;
//        this.col = board[0].length;
//        for(int i = 0; i < row; i++) {
//            for(int j = 0; j < col; j++) {
//                boolean[][] path = new boolean[row][col];
//                if(board[i][j] == 'O') {
//                    flag = true;
//                    dfs(board, i, j, path);
//                    if(flag) {
//                        board[i][j] = 'X';
//                    }
//                }
//            }
//        }
//    }
//    private void dfs(char[][] board, int x, int y, boolean[][] path) {
//        //出界，说明没有被完全包围
//        if(x < 0 || x >= row || y < 0 || y >= col) {
//            flag = false;//一旦遇到就说明不可行
//            return;
//        }
//        if(path[x][y]) {//没出界，但是当前路径走过
//            return;
//        }
//        //找到边界
//        if(board[x][y] == 'X') {
//            return;
//        }
//        path[x][y] = true;//表示当前路径已走过
//        dfs(board, x - 1, y, path);
//        dfs(board, x + 1, y, path);
//        dfs(board, x, y - 1, path);
//        dfs(board, x, y + 1, path);
//    }
//    //8.被围绕的区域(回溯优化——反向思考)
//    private int row;
//    private int col;
//    public void solve(char[][] board) {
//        //找到边上没有被包围的点进行标记
//        this.row = board.length;
//        this.col = board[0].length;
//        boolean[][] path = new boolean[row][col];
//        for(int i = 0; i < row; i++) {
//            for(int j = 0; j < col; j++) {
//                if((i == 0 || i == row - 1 || j == 0 || j == col - 1) &&
//                        (board[i][j] == 'O')) {//找到周围一圈未被包围的点
//                    dfs(board, i, j, path);//对这些点通过一个数组进行标记
//                }
//            }
//        }
//        //最后对没有标记的位置全部覆盖为X
//        for(int i = 0; i < row; i++) {
//            for(int j = 0; j < col; j++) {
//                if(!path[i][j] && board[i][j] != 'X') {
//                    board[i][j] = 'X';
//                }
//            }
//        }
//    }
//    private void dfs(char[][] board, int x, int y, boolean[][] path) {
//        //处理出界情况
//        if(x < 0 || x >= row || y < 0 || y >= col) {
//            return;
//        }
//        if(path[x][y]) {//没出界，但是当前路径走过
//            return;
//        }
//        //找到边界
//        if(board[x][y] == 'X') {
//            return;
//        }
//        path[x][y] = true;//表示当前路径已走过
//        dfs(board, x - 1, y, path);
//        dfs(board, x + 1, y, path);
//        dfs(board, x, y - 1, path);
//        dfs(board, x, y + 1, path);
//    }
//    //9.岛屿数量(回溯)
//    private void dfs(char[][] grid, int x, int y, boolean[][] path) {
//        if(x < 0 || x >= row || y < 0 || y >= col) {//出界
//            return;
//        }
//        if(grid[x][y] == '0') {//走到0
//            return;
//        }
//        if(path[x][y]) {//走过的地方
//            return;
//        }
//        path[x][y] = true;
//        dfs(grid, x - 1, y, path);
//        dfs(grid, x + 1, y, path);
//        dfs(grid, x, y - 1, path);
//        dfs(grid, x, y + 1, path);
//    }
//
//    private int row;
//    private int col;
//    public int numIslands(char[][] grid) {
//        this.row = grid.length;
//        this.col = grid[0].length;
//        int sum = 0;
//        boolean[][] path = new boolean[row][col];
//        for(int i = 0; i < row; i++) {
//            for(int j = 0; j < col; j++) {
//                if(!path[i][j] && grid[i][j] == '1') {//只有没走过的岛屿才继续走
//                    dfs(grid, i, j, path);
//                    sum++;
//                }
//            }
//        }
//        return sum;
//    }
//    //岛屿数量(回溯 + 优化【置零法】)
//    private void dfs(char[][] grid, int x, int y) {
//        if(x < 0 || x >= row || y < 0 || y >= col) {//出界
//            return;
//        }
//        if(grid[x][y] == '0') {//走到0
//            return;
//        }
//        grid[x][y] = '0';//置零
//        dfs(grid, x - 1, y);
//        dfs(grid, x + 1, y);
//        dfs(grid, x, y - 1);
//        dfs(grid, x, y + 1);
//    }
//
//    private int row;
//    private int col;
//    public int numIslands(char[][] grid) {
//        this.row = grid.length;
//        this.col = grid[0].length;
//        int sum = 0;
//        for(int i = 0; i < row; i++) {
//            for(int j = 0; j < col; j++) {
//                if(grid[i][j] == '1') {//只有没走过的岛屿才继续走
//                    dfs(grid, i, j);
//                    sum++;
//                }
//            }
//        }
//        return sum;
//    }
//    //10.岛屿的最大面积(回溯 + 优化)
//    private void dfs(int[][] grid, int x, int y) {
//        if(x < 0 || x >= row || y < 0 || y >= col || grid[x][y] == 0) {
//            return;
//        }
//        grid[x][y] = 0;
//        sum++;
//        dfs(grid, x - 1, y);
//        dfs(grid, x + 1, y);
//        dfs(grid, x, y - 1);
//        dfs(grid, x, y + 1);
//    }
//
//    private int row;
//    private int col;
//    private int sum;
//    public int maxAreaOfIsland(int[][] grid) {
//        //计算完岛屿就置零
//        this.row = grid.length;
//        this.col = grid[0].length;
//        int max = 0;
//        for(int i = 0; i < row; i++) {
//            for(int j = 0; j < col; j++) {
//                sum = 0;
//                if(grid[i][j] == 1) {
//                    dfs(grid, i, j);
//                }
//                if(sum > max) {
//                    max = sum;
//                }
//            }
//        }
//        return max;
//    }


}
//class Test {
//    public static void main(String[] args) {
//        Solution solution = new Solution();
//        solution.letterCombinations("23");
//    }
//}


class myCom implements Comparator<int[]> {
    public int compare(int[] a1, int[] a2) {
        return a1[1] - a2[1];
    }
}
